
bool search2DMatrix(vector<vector<int>> &matrix, int target) {
    int t = 0;
    int b = matrix.size() - 1;
    int row = -1;

    while (t <= b) {
        int m = (t + b) / 2;
        if (matrix[m][0] == target) {
            return true;
        }
        else if (matrix[m][0] < target) {
            if (m == matrix.size() - 1) {
                row = m;
                break;
            }
            else if (matrix[m + 1][0] == target) {
                return true;
            }
            else if (matrix[m + 1][0] < target) {
                t = m + 1;
            }
            else {
                row = m;
                break;
            }
        }
        else { // matrix[m][0] > target
            b = m - 1;
        }
    }

    if (row == -1) {
        return false;
    }

    // search target in row
    int l = 0;
    int r = matrix[row].size();
    while (l <= right) {
        int m = (l + r) / 2;
        if (matrix[row][m] == target) {
            return true;
        }
        else if (matrix[row][m] > target) {
            r = m - 1;
        }
        else {
            l = m + 1;
        }
    }

    return false;
}
